package com.Oct_TwentyTwo;

/**
 * 1319. 连通网络的操作次数
 * 用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
 *
 * 网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
 *
 * 给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。 
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-operations-to-make-network-connected
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/22 09:12
 */

public class Solution1319 {

    /**
     * 使用了并查集来进行操作
     */
    int[] father;

    public int makeConnected(int n, int[][] connections) {
        if (connections.length<n-1)
        {
            return -1;
        }
        father=new int[n];
        for (int i = 0; i < father.length; i++) {
            father[i]=i;
        }
        for (int[] connection :
                connections) {
            union(connection[0], connection[1]);
        }
        int count=0;
        for (int i=0;i<father.length;i++)
        {
            if (father[i]==i)
            {
                count++;
            }
        }
        return count-1;
    }

    private int find(int u)
    {
        return u==father[u]?u:(father[u]=find(father[u]));
    }

    private void union(int u,int v){
        u=find(u);
        v=find(v);
        if (u==v) return;
        father[v]=u;
    }

    public static void main(String[] args) {
        Solution1319 solution1319=new Solution1319();
        System.out.println(solution1319.makeConnected(4,new int[][]{{0,1},{0,2},{1,2}}));
    }

}
